#pragma once
#include "LinkedHashMap.h"
#include "LinkList.h"
#include "../strings/md5.h"

#ifndef BASSERT
#define BASSERT // TODO
#endif

#ifndef BLOGINFO
#define BLOGINFO
#endif

#ifndef WIN32
#include <sys/mman.h>
#else
#include <windows.h>
#endif

namespace qb{
	namespace base{
		typedef unsigned int uint;
		typedef unsigned char uchar;

		namespace util{
			bool S_CORE_EXPORT GetUpperExp2(int& num, unsigned short& bitcount);
			void ShiftMemory(uchar* mem, int bytes, int step)
			{
				// step为正表示向后移动,为负表示向左移动
				if (bytes > 0 && step != 0)
					memmove(mem + step, mem, bytes);
			}
			unsigned int InlineTime33Hash(const char *str, int len){
				unsigned int hash = 5381;
				const char* pend = str + len;
				while (str < pend){
					hash += (hash << 5) + (*str++);
				}
				return (hash & 0x7FFFFFFF);
			}
		}


		template<typename EntryType, typename KeyType, typename ValueType, int N = 256,bool MULTI=false>
		class DEL_ALIGN FStringChunk{

				enum{
					SSEBit  = 4,
					SSESize = 1 << SSEBit,	// 表示一次SSE搜索的项目个数

#ifdef WIN32
#ifdef _WIN64
					StartPos = N - 24,		//表示起始偏移量,也是最大,每次增加,偏移量会递减
#else
					StartPos = N - 16,		//表示起始偏移量,也是最大,每次增加,偏移量会递减
#endif
#else
					StartPos = N - 24,		//表示起始偏移量,也是最大,每次增加,偏移量会递减
#endif
											// 10 是末尾占据重要元信息的m_count,m_pos,m_mask,m_next等四个字段
				};

				typedef LinkedHashMapStat Stat;
				class EntryTypeDefault{	// 表示模板参数EntryType应该实现的接口
				public:
					uint GetHash()const;//计算当前键的哈希值
					int Bytes()const;//计算当前键值总共占据的内存,包括字符串末尾的0
					ValueType GetValue();//获取当前值,已经编码到结构体中
					void SetValue(const ValueType& v);//设置当前值,将值编码到结构体中,不会额外增加内存
					void CopyTo(const ValueType& value, char* buf, int bytes);//将当前键和值value,写入到内存buf中
				};
		public:
				typedef FStringChunk Chunk;
				typedef std::pair<const FStringChunk*, int> ChunkIndex;
				using HashPair = std::pair<std::size_t, uint8_t>;
		private:
				/*
				m_buffer的内存布局:
				uchar	m_tags[m_count];	// 标签
				uchar	m_pos[m_count];		// 偏移量

				......
				EntryType  第m_count-1个entry
				EntryType  第m_count-2个entry
				......
				EntryType  第1个entry
				EntryType  第0个entry
				*/
				
				uchar	m_count;		// 当前Chunk放入的字符串个数
				uchar	m_pos;			// 最后一个放入的字符串位置,即在m_buffer中的偏移量,也是索引
				ushort	m_pad1;
				uint	m_pad2;			// 
				uint	m_mask;			// 使用这个而不是搜索时计算,有明显的性能提升
				union{
					Chunk*	m_next;		// 下一个指针
					size_t	m_offset;	// 下一个Chunk在文件中的偏移量
				};
				uchar	m_buffer[StartPos];// 内存布局:m_count
		public:
			FStringChunk(FStringChunk* next) :m_next(next), m_count(0), m_pos(StartPos)
			{
				SetCount(0);
				static_assert(sizeof(FStringChunk) == N, "sizeof(FStringChunk) != N failed");
			}
			void SetCount(uchar count){ 
				m_count = count;
				m_mask = static_cast<unsigned>(~(~uint64_t{ 0 } << m_count));
			}
			void Clear()
			{
				//MEMSET(m_buffer, 0, N);
				m_next = nullptr;
				m_pos = StartPos;
				SetCount(0);
			}
			 FStringChunk* GetNext(){ return m_next; }
			 const FStringChunk* GetNext()const{ return m_next; }
			 void SetNext(FStringChunk* next){ m_next = next; }
			 void SetNextOffset(size_t offset){ m_offset = offset; }
			 size_t GetOffset()const{ return m_offset; }
			bool Get(const KeyType& key, const HashPair& hp, ValueType& value)const
			{
				int index= find(key, hp);
				if (index>=0)
				{
					value = itemAddr(index)->GetValue();
					return true;
				}
				return false;
			}
			bool Erase(const KeyType& key, const HashPair& hp)
			{
				int index = find(key, hp);
				if (index >= 0)
				{
					return EraseImpl(index);
				}
				return false;
			}
			bool EraseImpl(int index)
			{
				// 将该Chunk的指定索引的键值对删除,并同时恢复tags和偏移量数组
				if (index >= m_count || index < 0)return false;
				//Check();
				//FStringChunk* chunk = Clone();
				//again:
				uchar* tags = m_buffer;
				uchar* pos = m_buffer + m_count;
				// 将最前面的内容往后移动,使得index对应的内容被覆盖掉
				uchar delpos = pos[index];		// 旧的要删除的位置
				int bytes = delpos - m_pos;		//要移动的内存大小
				EntryType* et = itemAddr(index);
				int gap = EntryType::CalcBytes(et->GetKey(), et->GetValue());//要消除的空间
				util::ShiftMemory(m_buffer + m_pos, bytes, gap);

				// 将tags数组往左移动1个字节
				util::ShiftMemory(tags + index + 1, m_count - 1 - index, -1);

				//修正pos数组
				// 将偏移量左侧部分往左移动1个字节,右侧部分往左移动2个字节,且对应的值都增加gap
				for (int i = 0; i < index; i++){ 
					pos[i-1] = pos[i]<delpos?(pos[i]+gap):(pos[i]);
				}
				for (int i = index + 1; i < m_count; i++){
					pos[i - 2] = pos[i]<delpos ? (pos[i] + gap) : (pos[i]);
				}
				m_pos += gap;
				SetCount(m_count - 1);
				//if (!Check())
				//{
					//Restore(chunk);
					//goto again;
				//}
				//if (chunk)delete chunk;
				return true;
			}
			static  HashPair splitHash(std::size_t hash){
				uint8_t tag = (hash & 0x000000ff);// | 0x80;	// 使用低7个bit用于tag,第8个保留用于识别是否为空
				return std::make_pair(hash, tag);
			}
			FStringChunk* Clone()
			{
				FStringChunk* chunk = new FStringChunk(nullptr);
				memcpy(chunk, this, sizeof(FStringChunk));
				return chunk;
			}
			void Restore(FStringChunk* chunk)
			{
				memcpy(this, chunk, sizeof(FStringChunk));
			}
			bool Check()
			{
				BASSERT(m_pos <= StartPos);
				uchar* tags = m_buffer;
				uchar* pos = m_buffer + m_count;
				int nerror = 0;
				for (int i = 0; i < m_count; i++)
				{
					EntryType* et = itemAddr(i);
					KeyType kt = et->GetKey();
					std::size_t hash = kt.GetHash();
					if (splitHash(hash).second != tags[i])
						nerror++;
				}
				return nerror <= 0;
			}
			 int Count()const{ return m_count; }
			 bool IsEmpty()const{ return m_count <= 0; }
			 bool Exist(const KeyType& key, const HashPair& hp)const
			{
				int index = find(key, hp);
				return index >= 0;
			}
			 void PutAt(int index, const ValueType& value)
			{
				// 上层确定已经找到过,这里不做检查
				itemAddr(index)->SetValue(value);
			}
			 bool PutDirectly(const KeyType& key, const HashPair& hp, const ValueType& value)
			{
				// 为什么需要update:新建Chunk不需要重新搜索
				// 如果已经上层已经确定搜索过了,这里也不需要重新搜索
				// 外界已经探测到,key可以放进去了
				//Check();
				int bytes = EntryType::CalcBytes(key, value);
				uchar* tags = m_buffer;
				uchar* pos = m_buffer + m_count;
				uchar newpos = m_pos - bytes;
				//将偏移量数组向后移动1个字节
				util::ShiftMemory(pos, m_count, 1);
				//改写最后一个标签和偏移量,别将键值写入到指定位置
				tags[m_count] = hp.second;
				pos[m_count + 1] = newpos;
				EntryType* pentry = (EntryType*)(m_buffer + newpos);
				pentry->Build(key, value, bytes);
				m_pos -= bytes;
				SetCount(m_count + 1);

				//const EntryType* et = itemAddr(m_count - 1);
				//BASSERT(et && et->EqualKey(key));
				//Check();
				return true;
			}

			 bool PutWithSpace(const KeyType& key, const HashPair& hp, const ValueType& value)
			{
				// 为什么需要update:新建Chunk不需要重新搜索
				// 如果已经上层已经确定搜索过了,这里也不需要重新搜索
				if (m_count >= SSESize)//最多放16个
					return false;
				int bytes = EntryType::CalcBytes(key, value);
				int leftSpace = space();
				if (bytes+2 <= leftSpace)
				{
					return PutDirectly(key, hp, value);
				}
				// 放不下去,交给外部处理
				return false;
			}

			 bool PutWithSearch(const KeyType& key, const HashPair& hp, const ValueType& value, bool update)
			{
				// 为什么需要update:新建Chunk不需要重新搜索
				// 如果已经上层已经确定搜索过了,这里也不需要重新搜索
				if (update)
				{
					int index = find(key, hp);
					if (index >= 0)
					{
						itemAddr(index)->SetValue(value);
						return true;
					}
				}
				return PutWithSpace(key, hp, value);
			}
			void GetStat(Stat& st)
			{
				st.cache++;
				st.bytes += sizeof(FStringChunk)-space();
				st.count += m_count;

				int level = 1;
				auto next = m_next;
				while (next)
				{
					level++;
					next = next->GetNext();
				}
				if (st.max_level < level)
					st.max_level = level;
				st.sum_level += level;

				if (m_next)
					m_next->GetStat(st);
			}



			 const EntryType* itemAddr(int index)const{
				// 最开头m_count个uchar是tag数组
				// 然后m_count是偏移量数组
				// index>=0 && index<m_count
				const uchar*	posArray = m_buffer + m_count;
				uchar pos = posArray[index];
				return (const EntryType*)(m_buffer + pos);
			}
			 EntryType* itemAddr(int index){
				const uchar*	posArray = m_buffer + m_count;
				uchar pos = posArray[index];
				return (EntryType*)(m_buffer + pos);
			}
		protected:
			 TagVector const* tagVector(int nloop) const {
				return static_cast<TagVector const*>(static_cast<void const*>(&m_buffer[nloop<<SSEBit]));
			}
			 SparseMaskIter tagMatchIter(std::size_t needle, int nloop, unsigned int fullMask) const {
				FOLLY_SAFE_DCHECK((needle & 0x80) != 0, "");
				//unsigned int fullMask = m_mask;// static_cast<unsigned>(~(~uint64_t{ 0 } << count));
				//kFullMask = static_cast<unsigned>(~(~uint64_t{ 0 } << kCapacity))
				auto tagV = _mm_load_si128(tagVector(nloop));
				auto needleV = _mm_set1_epi8(static_cast<uint8_t>(needle));
				auto eqV = _mm_cmpeq_epi8(tagV, needleV);
				auto mask = _mm_movemask_epi8(eqV) & static_cast<unsigned>(fullMask);
				return SparseMaskIter{ mask };
			}

			 int space()const{
				// m_pos是上一次追加的位置,每次追加,m_pos都递减
				// 开头要占据两个长度为m_count的数组,分别是tags数组和偏移量数组
				// 中间的就是剩余空间
				return m_pos - m_count*sizeof(uchar) * 2;
			}
		public:
			template<bool MULTI2>
			 int findimpl(KeyType const& key, const HashPair& hp) const {
				 if(!MULTI2)
				 {
					// 如果计数超过16,则进行惰轮sse搜索,nloop表示当前轮次,nbase表示当前轮的基数索引
					// 在当前FStringChunk中查找对应的键值
					//prefetchAddr(m_buffer);
					// 经过测试,比MULTI为true时性能略高
					
					//unsigned int fullMask = m_mask;// static_cast<unsigned>(~(~uint64_t{ 0 } << count));
					//TagVector const* tagPtr = static_cast<TagVector const*>(static_cast<void const*>(m_buffer));
					//prefetchAddr((const char*)this + (N >> 1));
					//std::size_t needle = hp.second;
					//auto tagV = _mm_load_si128(tagPtr);
					//auto needleV = _mm_set1_epi8(static_cast<uint8_t>(needle));
					//auto eqV = _mm_cmpeq_epi8(tagV, needleV);
					//auto mask = _mm_movemask_epi8(eqV) & static_cast<unsigned>(fullMask);
					//SparseMaskIter hits(mask);

					prefetchAddr((const char*)this + (N >> 1));
					auto hits = tagMatchIter(hp.second, 0, m_mask);
					while (hits.hasNext()) {
						auto i = hits.next();
						const EntryType* et = itemAddr(i);
						if (et->EqualKey(key))
							return  i;
					}
					return -1;
				 }
				// 如果计数超过16,则进行惰轮sse搜索,nloop表示当前轮次,nbase表示当前轮的基数索引
				// 在当前FStringChunk中查找对应的键值
				// 支持在256字节中存储多轮查询,16个为一轮,性能测试表明16个就足够,多了反而降低
				int nloop = 0, nbase = 0, mcount = m_count;
				while (nbase < mcount)
				{
					int count = (nbase + SSESize) <= mcount ? SSESize : (mcount - nbase);
					//prefetchAddr(m_buffer);
					unsigned int fullMask = static_cast<unsigned>(~(~uint64_t{ 0 } << count));
					auto hits = tagMatchIter(hp.second, nloop, fullMask);
					while (hits.hasNext()) {
						auto i = hits.next();
						if (itemAddr(i + nbase)->EqualKey(key))
							return nbase + i;
					}
					nloop++;
					nbase += SSESize;
				}
				return -1;
			}

			 int find(KeyType const& key, const HashPair& hp) const {
				// 如果计数超过16,则进行惰轮sse搜索,nloop表示当前轮次,nbase表示当前轮的基数索引
				// 在当前fstringchunk中查找对应的键值
				bool sse2 = sse::supports_sse2();
				return sse2 ? findimpl<MULTI>(key, hp) : findWithoutSSE(key);
			}
			 int findWithoutSSE(KeyType const& key)const{
				for (int i = 0; i < m_count; i++)
				{
					if (itemAddr(i)->EqualKey(key))
						return i;
				}
				return -1;
			}
		};
		//static_assert(sizeof(FStringChunk) == 256, "");

		
		struct  S_CORE_EXPORT StringView{			// 用于轻量级传递参数
			int			len;
			const char*	str;
			StringView() :len(0), str(nullptr){}
			StringView(const StringView& view) :len(view.len), str(view.str){}
			StringView(const char* s) :str(s), len(s ? strlen(s) : 0){}
			StringView(const char* s, int l) :str(s), len(l){}
			StringView& operator=(const StringView& view){
				len = view.len;
				str = view.str;
				return *this;
			}
			bool operator==(const StringView& view)const{
				return len == view.len && memcmp(str, view.str, len) == 0;
			}
			bool operator!=(const StringView& view)const{
				return !(len == view.len && memcmp(str, view.str, len) == 0);
			}
			 uint GetHash()const//计算当前键的哈希值
			{
				return util::InlineTime33Hash(str, len);
			}
			 int Bytes()const//计算当前键值总共占据的内存,包括字符串末尾的0
			{
				return sizeof(uint) + len + 1;
			}
		};
		struct S_CORE_EXPORT StringIntEntry{		// 用于紧凑式存储内容
			uint		len : 8;		// 最大长度为256
			uint		id : 24;		// 最大支持2^24即1600w的数字
			char		str[4];		// 注意,str实际内容长度一般超过这个数组
		public:
			StringIntEntry() :len(0), id(0){ str[0] = '\0'; }
			 uint GetValue()const//获取当前值,已经编码到结构体中
			{
				return id;
			}
			 StringView GetKey()const{ return StringView(str, len); }
			 void SetValue(const uint& v)//设置当前值,将值编码到结构体中,不会额外增加内存
			{
				id = v;
			}
			 void Build(const StringView& key, const uint& value, int bytes)//将当前键和值value,写入到内存buf中
			{
				//BASSERT(key.Bytes() == bytes);
				len = key.len;
				id = value;
				memcpy(str, key.str, len);
				str[len] = '\0';
			}
			static  int  CalcBytes(const StringView& key, const uint& value)
			{
				return key.Bytes();
			}
			 bool EqualKey(const StringView& view)const
			{
				//if (len != view.len)return false;
				//const char* p1 = view.str;
				//const char* p2 = str;
				//const char* end = str + len;
				//while (p2 < end && *p1++ == *p2++){}
				//return true;
				//return len == view.len && 0==A_memcmp(view.str, str, len);
				return len == view.len && 0 == memcmp(view.str, str, len);
				//return len == view.len && strncmp(view.str, str, len) == 0;
				//return len == view.len && EqualMemoryComp(view.str, str, len);
			}

		};

		struct S_CORE_EXPORT StringIntPair{		// 用于紧凑式存储内容
			uint		id;			// 最大支持2^24即1600w的数字
			char		str[4];		// 注意,str实际内容长度一般超过这个数组
		public:
			StringIntPair() :id(0){ str[0] = '\0'; }
			 uint GetValue()const//获取当前值,已经编码到结构体中
			{
				return id;
			}
			 StringView GetKey()const{ return StringView(str, strlen(str)); }
			 void SetValue(const uint& v)//设置当前值,将值编码到结构体中,不会额外增加内存
			{
				id = v;
			}
			 void Build(const StringView& key, const uint& value, int bytes)//将当前键和值value,写入到内存buf中
			{
				//BASSERT(key.Bytes() == bytes);
				id = value;
				memcpy(str, key.str, key.len);
				str[key.len] = '\0';
			}
			 bool EqualKey(const StringView& view)const
			{
				// 经过测试strcmp比strncmp速度还快
				//return len == view.len && 0==A_MEMCMP(view.str, str, len);
				return strcmp(str, view.str) == 0;
				//return memcmp(view.str, str, len);
				//return len == view.len && strncmp(view.str, str, len) == 0;
				//return len == view.len && EqualMemoryComp(view.str, str, len);
			}

		};

		template<int N>
		class PagedPool{
			enum{
				Magic = 0xfed0cfad,
				PageSize = 64 * 1024,
				EmptyMask = 0xffffffff
			};
			struct ItemInfo{
				char	data[N];
			};
			class PageHead{
				PageHead*	next;		// 单链表
				PageHead*	prev;
				uint		magic;		// 常量值,用于检测问题
				uint		bytes;		// 整体Page的尺寸内存,通常是64kb	
				int			size;		// 每个的大小
				int			count;		// 实际放入的个数
				int			capcity;	// 实际可容纳的个数
				int			nbitmap;	// bitmap数组的长度
				int			offset;		// 第一个item的偏移量,在bitmap数组之后
				uint		bitmap[1];	// 实际长度由nbitmap指定,每一个bit为1表示对应位置是否被占用
			public:
				PageHead() :next(nullptr), prev(nullptr), magic(Magic), bytes(PageSize), size(N), count(0){
					for (int i = 1; i < 16; i++)
					{
						offset = i*size;
						capcity = (bytes - offset) / size;
						nbitmap = capcity / 32;
						if (capcity % 32 != 0)
							nbitmap++;

						if (sizeof(PageHead) + (nbitmap - 1)*sizeof(uint) < (size_t)size)
							break;
					}
					for (int i = 0; i < nbitmap; i++)
						bitmap[i] = EmptyMask;
				}
				PageHead* GetNext()const{ return next; }
				PageHead* GetPrev()const{ return prev; }
				void SetNext(PageHead* n){ next = n; }
				void SetPrev(PageHead* p){ prev = p; }

				bool Check()const{ return magic == Magic && bytes == PageSize && size == N; }
				bool IsFull()const{ return count >= capcity; }
				bool IsEmpty()const{ return count <= 0; }
				void* Alloc()
				{
					if (count >= capcity)
						return nullptr;
					int index = FirstEmpty();
					if (index < 0 || index >= capcity)
						return nullptr;
					void* ptr = At(index);
					Set(index, true);
					count++;
					return ptr;
				}
				bool Free(void* ptr, int len)
				{
					const char* base = (const char*)this;
					if (ptr < base || ptr >= base + bytes || size != len)
						return false;
					int index = (((const char*)ptr - base) - offset) / size;
					if (ptr == At(index))
					{
						Set(index, false);
						count--;
						return true;
					}
					return false;
				}
			protected:
				void* At(int index)
				{
					const char* base = (const char*)this;
					return (void*)(base + offset + index*size);
				}
				void Set(int index, bool used)
				{
					int pos = index / 32;
					int bit = index - pos * 32;
					uint flag = ((uint)1) << bit;
					if (used)
						bitmap[pos] &= ~flag; //设置0
					else
						bitmap[pos] |= flag;//设置1
				}
				int FirstEmpty()const{
					for (int i = 0; i < nbitmap; i++)
					{
						FirstEmptyInMask mask(bitmap[i]);
						if (mask.hasIndex())
						{
							return mask.index() + i * 32;
						}
					}
					return -1;
				}
			};
			DoubleLinkList<PageHead>	m_slist;	// 有空位的
			DoubleLinkList<PageHead>	m_full;		// 已经满了的
		public:
			PagedPool(){}
			~PagedPool()
			{
				FreePage(m_slist.GetHead());
				FreePage(m_full.GetHead());
			}
			void Swap(PagedPool& other){
				m_slist.Swap(other.m_slist);
				m_full.Swap(other.m_full);
			}
			void* Alloc()
			{
				PageHead* head = m_slist.GetHead();
				if (!head)
				{
					m_slist.InsertHead(NewPage());
					head = m_slist.GetHead();
				}

				//BASSERT(!head->IsFull());
				void* ptr = head->Alloc();
				if (head->IsFull())
				{
					m_full.Append(m_slist.PickHead());
				}
				return ptr;
			}
			void Free(void* ptr, int size)
			{
				// PageHead都是以PageSize对齐
				uintptr_t addr = (uintptr_t)(ptr);
				addr = (addr / PageSize)*PageSize;
				PageHead* page = (PageHead*)addr;

				if (page)
				{
					BASSERT(page->Check());
					bool s1 = m_slist.Contain(page);
					bool f1 = m_full.Contain(page);
					BASSERT(s1 || f1);
					bool full = page->IsFull();
					bool suc = page->Free(ptr, size);
					if (suc)
					{
						if (full)
						{
							// 将page从m_full中迁移到m_slist中
							m_full.Remove(page);
							m_slist.Append(page);
						}
						else if (page->IsEmpty())
						{
							m_slist.Remove(page);
							FreePage(page);
						}
					}
					else
					{
						BLOGINFO("[CACHE]page Free item failed");
					}
				}
				else
				{
					BLOGINFO("[CACHE]invalid PageHead:0x%08x", page);
				}
			}
			int GetBytes()const{
				return (m_slist.GetCount() + m_full.GetCount())*PageSize + sizeof(*this);
			}
		protected:
			PageHead* NewPage()
			{
				#ifdef WIN32
				void* ptr = VirtualAlloc(NULL, PageSize, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
				#else
				//TODO: address is 0?!
				void* ptr = malloc(PageSize);
				#endif
				return new (ptr)PageHead();
			}
			void FreePage(PageHead* page)
			{
				while (page)
				{
					PageHead* temp = page;
					page = page->GetNext();
					#ifdef WIN32
					VirtualFree(temp, 0, MEM_RELEASE);
					#else
					free(temp);
					#endif
				}
			}

		};

		class HashmapHint{
			int		m_capcity, m_keylen;
		public:
			HashmapHint(int capcity, int keylen) :m_capcity(capcity), m_keylen(keylen){}
			~HashmapHint(){}
			int Capcity()const{ return m_capcity; }
			int KeyLength()const{ return m_keylen; }
		};
		template<
			typename EntryType,
			typename KeyType,
			typename ValueType,
			typename CacheLine = FStringChunk<EntryType, KeyType, ValueType, 256>
		>
		class StringIntHashMap{
		public:
			enum{
				Magic = 0xABFE,
				kCacheSize = 64,		// 一级缓存行大小通用值为64字节
				kBitCountMin = 6,		//
				kBitCountMax = 24,		// 限制哈希插槽最大值为1<<24,即16777216
				//kKeyCount = (kCacheSize - sizeof(void*)) / sizeof(EntryType),
				//一个缓存行CacheLine中放置几个值项
			};
			enum{
				kFlagUsePool		=	0x0001,			// 是否开启虚拟内存池分配器
														// 使用后,构建时间和销毁时间略有缩短,幅度不大
				kFlagUseExpand		=   0x0002,			// 是否允许自动扩展
				kFlagListForBlank	=	0x0004,			// 是否允许整个单链表查找空位
														// 开启后减少内存,但是构建速度会慢
			};
			typedef LinkedHashMapStat Stat;
		protected:
			typedef CacheLine* SlotPtr;
			typedef std::vector<SlotPtr> SlotArray;
			typedef typename CacheLine::ChunkIndex ChunkIndex;
			struct FileHead{	// 文件头部
				uint		magic;			//
				uint		hashoffset;		//
				uint		hashlength;		//
				uint		chunkoffset;	//
				uint		chunksize;		//
				uint		chunkcount;		//
				uint		keycount;		//
			};
			// 使用PagedPool的好处:内存碎片少,销毁时间非常短,性能上并没有额外的优势
			typedef PagedPool<sizeof(CacheLine)> CachePool;
			
		protected:
			SlotArray	m_slots;		// m_slot_count个,12个字节
			CachePool	m_pool;			// 虚拟内存池分配器,24个字节
			ushort		m_flag;			// 功能标志位,后续可以考虑用模板policy实现,性能更好,见folly的F14Table
			ushort		m_bitcount;		// 如果插槽长度刚好是2的n次幂,那么m_bitcount==n,否则为0	
			int			m_count;		// 真实放入的键值对个数
			int			m_nodecount;	// CacheLine的总个数
			int			m_bitmask;		// (((uint)1)<<m_bitcount)-1,用来计算哈希位置
		public:
			StringIntHashMap(int slotcapcity = 1024,bool usePool=true,bool useExpand=true) :m_count(0), m_nodecount(0),
				m_bitcount(0), m_bitmask(0), m_flag(0)
			{
				//m_flag |= kFlagListForBlank;
				if (usePool)m_flag |= kFlagUsePool;
				//if (useExpand)m_flag |= kFlagUseExpand;

				// debug下vector大小是16,
				//static_assert(sizeof(SlotArray) == 16,"vector");
				//static_assert(sizeof(*this) == 40 + 16,"StringIntHashMap");
				// 经过测试,对于20w的数据1w个插槽是合适的,效率和内存综合最佳
				//NameDict插入时间性能有待优化, 改成哈希表可能更好
				//	CacheLine是整块的内存, 可以预先提前分配
				//	bkey可以使用编码进一步减少尺寸
				//	参考F14Map, 使用并行搜索, 增大CacheLine尺寸会导致空间浪费
				//F14Map并行搜索 : 为每个节点生成一个1个字节的哈希值, 将16个节点的哈希值凑成一个128位值, 然后使用intel sse指令
				//			 一次性搜索16个

				//确保哈希长度为2的m_bitcount次幂,这样计算位置速度最快
				if (util::GetUpperExp2(slotcapcity, m_bitcount))
					m_bitmask = (1 << m_bitcount) - 1;
				m_slots.reserve(slotcapcity);
				for (int i = 0; i < slotcapcity; i++)
					m_slots.emplace_back(nullptr);
			}
			~StringIntHashMap()
			{
				Clear();
			}
			int GetCount()const{ return m_count; }
			int GetLength()const{ return m_slots.capacity(); }
			int GetSlotCount()const{ return m_slots.size(); }
			double GetLoadRatio()const{
				return m_count*1.0 / (m_nodecount*CacheLine::kKeyCount);
			}
			using HashPair = std::pair<std::size_t, uint8_t>;
			using size_type = size_t;
		protected://迭代器
			int CalcCount()const{
				int ncount = 0;
				for (int i = 0; i < (int)m_slots.size(); i++)
				{
					const CacheLine* cache = m_slots[i];
					while (cache)
					{
						ncount += cache->Count();
						cache = cache->GetNext();
					}
				}
				return ncount;
			}
			ChunkIndex Next(int& slot, const ChunkIndex& it)const{
				const CacheLine* cache = it.first;
				//BASSERT(cache);
				if (it.second + 1 < cache->Count())
					return ChunkIndex{ cache, it.second + 1 };
				cache = cache->GetNext();
				if (cache && cache->Count() > 0)
					return ChunkIndex{ cache, 0 };
				while (slot + 1 < (int)m_slots.size())
				{
					slot++;
					cache = m_slots[slot];
					if (cache)
					{
						return ChunkIndex{ cache, 0 };
					}
				}
				// 模拟end()
				slot = 0;
				return ChunkIndex{ nullptr, -1 };
			}
		public://std::map的类似接口
			class iterator{
				const StringIntHashMap*	m_owner;	// 拥有者
				int					m_slot;		// 一个个插槽来遍历
				ChunkIndex			m_itor;		// 该插槽上的单链表位置
			public:
				iterator(const StringIntHashMap* owner) :m_owner(owner), m_slot(0), m_itor(nullptr, -1){}
				iterator(const StringIntHashMap* owner, int slot, const ChunkIndex& ci) :m_owner(owner), m_slot(slot), m_itor(ci){}
				iterator(const iterator& it) :m_owner(it.m_owner), m_slot(it.m_slot), m_itor(it.m_itor){}
				iterator(iterator&& it) :m_owner(nullptr), m_slot(0), m_itor(nullptr, -1){
					std::swap(m_owner, it.m_owner);
					std::swap(m_slot, it.m_slot);
					std::swap(m_itor, it.m_itor);
				}
				iterator operator=(iterator&& it)
				{
					std::swap(m_owner, it.m_owner);
					std::swap(m_slot, it.m_slot);
					std::swap(m_itor, it.m_itor);
					return *this;
				}
				iterator& operator=(const iterator& it){
					m_owner = it.m_owner;
					m_slot = it.m_slot;
					m_itor = it.m_itor;
					return *this;
				}
				bool operator!=(const iterator& it)const{
					return m_owner != it.m_owner || m_slot != it.m_slot || m_itor != it.m_itor;
				}
				bool operator==(const iterator& it)const{
					return m_owner == it.m_owner && m_slot == it.m_slot && m_itor == it.m_itor;
				}
				iterator operator++(){//前置:更改自身,再返回
					if (m_owner)
					{
						m_itor = m_owner->Next(m_slot, m_itor);
					}
					return *this;
				}
				KeyType first()const{//可能会抛出异常,因为迭代器可能失效
					return m_itor.first->itemAddr(m_itor.second)->GetKey();
				}
				ValueType second()const{//可能会抛出异常,因为迭代器可能失效
					return m_itor.first->itemAddr(m_itor.second)->GetValue();
				}
			};
			size_t size()const{ return m_count; }
			iterator begin()const
			{
				for (int i = 0; i < (int)m_slots.size(); i++)
				{
					const CacheLine* cache = m_slots[i];
					while (cache)
					{
						if (!cache->IsEmpty())
						{
							return iterator(this, i, ChunkIndex{ cache, 0 });
						}
					}
				}
				return iterator(this);
			}
			iterator end()const
			{
				return iterator(this);
			}
			iterator find(const KeyType& key)const
			{
				auto hp = splitHash(key.GetHash());
				auto it = Find(key, hp);
				return iterator(this, 0, it);
			}
			size_type erase(const KeyType& key)
			{
				return Erase(key) ? 1 : 0;
			}
		public:
			bool Get(const KeyType& key, ValueType& value)
			{
				auto hp = splitHash(key.GetHash());
				auto it = Find(key, hp);
				if (it.first)
				{
					value = it.first->itemAddr(it.second)->GetValue();
					return true;
				}
				return false;
			}
			void GetValues(std::vector<ValueType>& values)
			{
				values.clear();
				values.reserve(GetCount());
				for (int i = 0; i < (int)m_slots.size(); i++)
				{
					const CacheLine* cache = m_slots[i];
					while (cache)
					{
						for (int k = 0; k < cache->Count();k++)
						{
							const EntryType* et = cache->itemAddr(k);
							values.push_back(et->GetValue());
						}
						cache = cache->GetNext();
					}
				}
			}
			 int PutAtSlot(const KeyType& key, const HashPair& hp, const ValueType& value)
			{
				// 将键值写入到hp计算到的插槽中,成功返回插槽编号,否则返回-1
				int slot = GetPos(hp);
				SlotPtr cache = m_slots[slot];
				if (cache && cache->PutWithSpace(key, hp, value))
				{
					m_count++;
					return slot;
				}
				return -1;
				//开启kFlagListForBlank后的代码;
				//鉴于kFlagListForBlank对内存影响很小,不放开使用
				//while (cache)
				//{
				//	if (cache->Put(key, hp, value, false))
				//	{
				//		m_count++;
				//		return slot;
				//	}
				//	cache = (kFlagListForBlank&m_flag)?cache->GetNext():nullptr;
				//}
				//return -1;
			}
			void Put(const KeyType& key, const ValueType& value)
			{
				auto hp = splitHash(key.GetHash());
				auto it = Find(key, hp);
				if (it.first)
				{
					// 找到了必定能写入成功,因为value是固定尺寸大小
					(const_cast<CacheLine*>(it.first))->PutAt(it.second, value);
					return;
				}

				// 第一个不能写入,后续的即使有空间,为了性能考虑也不做尝试
				int slot = GetPos(hp);
				SlotPtr cache = m_slots[slot];
				if (cache && cache->PutWithSpace(key, hp, value))
				{
					m_count++;
					return ;
				}
				if ((m_flag&kFlagUseExpand) && (size_t)m_nodecount >= (m_slots.size() << 1))
				{
					ushort bitcount = 0;
					int capcity = m_slots.size()+1;
					util::GetUpperExp2(capcity, bitcount);
					if (ExpandSlots(capcity, m_flag&kFlagUsePool))
					{
						slot = GetPos(hp);
						cache = m_slots[slot];
						if (cache && cache->PutWithSpace(key, hp, value))
						{
							m_count++;
							return ;
						}
					}
				}
				cache = NewCache(m_slots[slot]);
				m_slots[slot] = cache;
				cache->PutDirectly(key, hp, value);
				m_nodecount++;
				m_count++;
			}
			bool Erase(const KeyType& key)
			{
				bool suc = false;
				SlotPtr prev = nullptr;
				auto hp = splitHash(key.GetHash());
				int slot = GetPos(hp);
				SlotPtr cache = m_slots[slot];
				while (cache)
				{
					suc = cache->Erase(key, hp);
					if (suc)
					{
						if (cache->IsEmpty())
						{
							if (prev == nullptr)
								m_slots[slot] = cache->GetNext();
							else
								prev->SetNext(cache->GetNext());
							DelCache(cache);
							m_nodecount--;
						}
						break;
					}
					prev = cache;
					cache = cache->GetNext();
				}
				if (suc)
					m_count--;
				return suc;
			}
			bool Exist(const KeyType& key)const
			{
				auto it = Find(key, splitHash(key.GetHash()));
				return it.first != nullptr;
			}
			void Expand(int keycapcity,double keyBytes=0.0,bool usePool=true)
			{
				// keycapcity是要放置的key大概总共有多少个
				// 首先预估一下每个键值的平均长度
				// 这里需要计算一下最佳插槽个数
				if (keyBytes <= 1.0)
				{
					keyBytes = PredictKeyLenth();
					BLOGINFO("[CACHE]calc keylen=%.2f", keyBytes);
				}
				int capcity = CalcSlotLength(keycapcity,keyBytes, 0.9);
				if (capcity <= (int)m_slots.capacity())
					return;
				ExpandSlots(capcity,usePool);
			}
			void Swap(StringIntHashMap& temp)
			{
				std::swap(m_slots, temp.m_slots);
				m_pool.Swap(temp.m_pool);
				std::swap(m_flag, temp.m_flag);
				std::swap(m_bitcount, temp.m_bitcount);

				std::swap(m_count, temp.m_count);
				std::swap(m_nodecount, temp.m_nodecount);
				std::swap(m_bitmask, temp.m_bitmask);
			}

			bool Load(const char* buf, int fsize)
			{
				// 从磁盘文件中重新加载此数据
				if (buf == nullptr || fsize < sizeof(FileHead))
					return false;
				const FileHead* head = (const FileHead*)buf;
				if (head->magic != Magic)return false;
				if (fsize != head->chunkoffset + head->chunksize*head->chunkcount)
					return false;
				if (sizeof(CacheLine) != head->chunksize)
					return false;
				int md5size = sizeof(MD5::tMD5);
				int offset = sizeof(uint) + md5size;
				uint* slots = (uint*)(buf + head->hashoffset);
				//MD5::tMD5 md5Check;
				//MD5::FromString((const char*)slots, head->hashlength*sizeof(uint), md5Check, md5size);
				//if (strcmp(md5Check, head->md5) != 0)
				//	return false;

				StringIntHashMap temp(head->hashlength);

				CacheLine* caches = (CacheLine*)(buf + head->chunkoffset);
				for (int i = 0; i < (int)head->hashlength; i++)
				{
					if (slots[i] == 0)continue;
					const CacheLine* cache = (const CacheLine*)(buf + slots[i]);
					CacheLine* prev = nullptr;
					while (cache)
					{
						// 处理内存中的
						CacheLine* cur = temp.NewCache(nullptr);
						if (prev == nullptr)
							temp.GetSlotHead(i) = cur;
						else
							prev->SetNext(cur);
						prev = cur;
						memcpy(cur, cache, sizeof(CacheLine));
						cur->SetNext(nullptr);

						// 处理从文件中加载的
						if (cache->GetOffset() == 0)
							break;
						cache = (const CacheLine*)(buf + cache->GetOffset());
					}
				}
				temp.m_count = head->keycount;
				temp.m_nodecount = head->chunkcount;
				Swap(temp);
				return true;
			}
			int Save(char* buf, int capcity)const
			{
				class PagedFileWriter{
					char*	m_buf;
					int		m_capcity;
					int		m_filepos;
					int		m_used;
					void*	m_file;
				public:
					void Append(const char* buf, int size)
					{

					}
					void Write(int pos, const char* buf, int size)
					{
						// 从位置pos开始,写入内存buf,如果buf为0,那么写入内容0

					}
				};
				class MemoryWriter{
					char*	m_buf;
					int		m_capcity;
					int		m_filepos;
				public:
					MemoryWriter(char* buf, int capcity) :m_buf(buf), m_capcity(capcity), m_filepos(0){}
					void Append(const char* buf, int size)
					{
						if (buf)
							memcpy(m_buf + m_filepos, buf, size);
						else
							memset(m_buf + m_filepos, 0, size);
						m_filepos += size;
					}
					void Write(int pos, const char* buf, int size)
					{
						// 从位置pos开始,写入内存buf,如果buf为0,那么写入内容0
						memcpy(m_buf + pos, buf, size);
					}
				};
				MemoryWriter fwriter(buf,capcity);
				int nfsize = CalcFileSize();
				if (buf == nullptr)
					return nfsize;
				if (capcity < nfsize)
					return -1;

				const int ncachesize = sizeof(CacheLine);
				int headsize = sizeof(FileHead) + m_slots.size()*sizeof(SlotPtr);
				if (headsize%ncachesize != 0)//以ncachesize上对齐
					headsize = (headsize / ncachesize + 1)*ncachesize;

				//MEMSET(buf, 0, nfsize);
				//SlotPtr caches = (SlotPtr)(buf + headsize);//连续CacheLine数组,每个都是256
				int index = 0, keycount = 0;
				std::vector<uint> slots; slots.reserve(m_slots.size());//连续哈希插槽数组,只有偏移量

				
				FileHead head;
				memset(&head, 0, sizeof(FileHead));
				head.chunkcount = m_nodecount;
				head.chunkoffset = headsize;
				head.chunksize = sizeof(CacheLine);
				head.hashoffset = sizeof(FileHead);
				head.hashlength = m_slots.size();
				head.keycount = m_count;
				head.magic = Magic;

				fwriter.Append((const char*)&head, sizeof(FileHead));
				fwriter.Append(0, headsize - sizeof(FileHead));//填充0
				for (int i = 0; i < (int)m_slots.size(); i++)
				{
					SlotPtr cache = m_slots[i];
					slots.emplace_back(cache ? (headsize + index*ncachesize) : 0);
					// 严格顺序访问
					while (cache)
					{
						SlotPtr next = cache->GetNext();
						uint nextoffset = next ? (headsize + (index + 1)*ncachesize) : 0;
						//memcpy(&(caches[index]), cache, sizeof(CacheLine));
						cache->SetNextOffset(nextoffset);
						fwriter.Append((const char*)cache, sizeof(CacheLine));
						cache->SetNext(next);//还原

						//caches[index].SetNextOffset(nextoffset);
						keycount += cache->Count();
						cache = next;
						index++;
					}
				}
				//BASSERTS(m_count == keycount, "%d!=%d", m_count, keycount);
				// 写入头部
				
				int md5size = sizeof(MD5::tMD5);
				int offset = sizeof(uint) + md5size;

				// 写入哈希数组
				fwriter.Write(sizeof(FileHead), (const char*)&slots[0], sizeof(uint)*m_slots.size());
				//memcpy(buf + sizeof(FileHead), &slots[0], sizeof(uint)*m_slots.size());
				//delete[] slots;
				// 结果表明,整体MD5非常消耗资源,只需要计算哈希数组即可
				// 8ms
				//MD5::FromString((const char*)slots, m_slots.size()*sizeof(uint), head->md5, md5size);
				return nfsize;
			}
			bool Equal(const StringIntHashMap& cont)const
			{
				auto it = begin();
				auto it2 = cont.begin();
				auto e1 = end(), e2 = cont.end();
				if (m_count != cont.m_count)
					return false;
				int index = 0;
				int n1 = CalcCount();
				int n2 = cont.CalcCount();
				for (; it != e1 && it2 != e2; ++index, ++it, ++it2)
				{
					if (it.first() != it2.first())
						return false;
					if (it.second() != it2.second())
						return false;
				}
				if (it != e1 || it2 != e2)
					return false;
				return true;
			}
			int CalcFileSize()const
			{
				const int ncachesize = sizeof(CacheLine);
				int fsize = sizeof(FileHead) + m_slots.size()*sizeof(SlotPtr);
				if (fsize%ncachesize != 0)
					fsize = (fsize / ncachesize + 1)*ncachesize;
				fsize += GetNodeCount()*ncachesize;
				return fsize;
			}
			int CalcSlotLength(int keycapcity, double keyBytes, double expectLoad)const
			{
				// 根据每个键值的平均长度,和期望负载,计算合适的哈希长度
				double avgChunkKeyCount = sizeof(CacheLine)*1.0 / (keyBytes + 1 + 1);
				int slotLength = (int)(keycapcity / (expectLoad*avgChunkKeyCount));
				unsigned short  bitcount = 0;
				util::GetUpperExp2(slotLength, bitcount);
				return slotLength;
			}
		protected:
			bool ExpandSlots(int slotCount,bool usePool=true)
			{
				// 假设slotCount是2的n此幂,不做检查
				if (slotCount == m_slots.size())
				{
					BLOGINFO("[CACHE]expand failed %d", slotCount);
					return false;
				}
				StringIntHashMap temp(slotCount);
				temp.m_flag = m_flag;
				if (usePool)m_flag |= kFlagUsePool;
				else m_flag &= ~kFlagUsePool;
				SlotPtr head = nullptr;		// 使用原先哈希表的CacheLine
				for (int i = 0; i < (int)m_slots.size(); i++)
				{
					SlotPtr next = m_slots[i];
					m_slots[i] = nullptr;
					while (next)
					{
						SlotPtr cache = next;
						next = next->GetNext();
						cache->SetNext(nullptr);

						// 如果m_usepool开启,那么不需要转移CacheLine内存,此时useCacheList永远为空
						SlotPtr useCacheList = (m_flag&kFlagUsePool) ? nullptr : head;
						for (int i = 0; i < cache->Count(); i++)
						{
							const EntryType* et = cache->itemAddr(i);
							useCacheList = temp.PutWithCache(et->GetKey(), et->GetValue(), useCacheList);
						}
						// 放到空闲单链表中
						cache->SetNext(useCacheList);
						head = cache;
					}
				}

				// 清除head的单链表,如果m_usepool开启,则析构时一次性销毁,而不是一个个销毁
				int nleft = 0;
				if (!(m_flag&kFlagUsePool))
				{
					while (head)
					{
						CacheLine* temp = head;
						head = head->GetNext();
						DelCache(temp);
						nleft++;
					}
				}
				BLOGINFO("[CACHE]expand %d ==> %d  ntotal:%d nleft:%d", m_slots.size(), slotCount,m_nodecount, nleft);
				Swap(temp);
				return true;
			}

			double CalcKeyLength()const{
				int keycount = 0;
				int keysize = 0;
				for (int i = 0; i < (int)m_slots.size(); i++)
				{
					const CacheLine* cache = m_slots[i];
					while (cache)
					{
						if (cache->Count() > 0)
						{
							keysize+=sizeof(CacheLine) - cache->space();
							keycount += cache->Count();
						}
						cache = cache->GetNext();
					}
				}
				return keycount <= 0 ? 0 : (keysize*1.0 / keycount);
			}
			double PredictKeyLenth()const
			{
				//预估当前的键的长度,只取最多1000个
				int firstPos = 0;
				int slotStep = 3;
				int slotLen = m_slots.size();
				int keycount = 0, keycapcity = 128;
				int bytes = 0;
				const double dft_bytes = 24.0;
				if (m_count <= 0)
					return dft_bytes;//假设平均长度24;
				for (int i = firstPos; i < slotLen;i+=slotStep)
				{
					if (m_slots[i] == nullptr)continue;
					const CacheLine* cache = m_slots[i];
					
					for (int k = 0; k < cache->Count(); k++)
					{
						bytes+=cache->itemAddr(k)->GetKey().Bytes();
					}
					keycount += cache->Count();
					if (keycount > keycapcity)
						break;
				}
				if (keycount <= 0)
				{
					iterator et = end();
					for (auto it = begin(); it != et && keycount<keycapcity; ++it)
					{
						bytes += it.first().Bytes();
						keycount++;
					}
				}
				return keycount <= 0 ? dft_bytes : (bytes*1.0 / keycount);
			}
			CacheLine* NewCache(CacheLine* next)
			{
				if (m_flag&kFlagUsePool)
					return new (m_pool.Alloc()) CacheLine(next);
				else
#if defined (CCORE_MAC)
                {
                    SlotPtr p;
                    NEW_CACHE(p, CacheLine, next);
                    return p;
                }
#else
                    return NEW_CACHE(CacheLine, next);
#endif
			}
			void DelCache(CacheLine* cache)
			{
				if (m_flag&kFlagUsePool)
					m_pool.Free(cache, sizeof(CacheLine));
				else DEL_CACHE(CacheLine, cache);
			}
			SlotPtr& GetSlotHead(int index){
				return m_slots[index];
			}
			void Clear()
			{
				if (!(m_flag&kFlagUsePool))
				{
					for (int i = 0; i < (int)m_slots.size(); i++)
					{
						CacheLine* cache = m_slots[i];
						while (cache)
						{
							CacheLine* temp = cache;
							cache = cache->GetNext();
							DelCache(temp);
							m_nodecount--;
						}
					}
				}
				m_slots.clear();
			}
			int GetNodeCount()const{
				int ncount = 0;
				for (int i = 0; i < (int)m_slots.size(); i++)
				{
					SlotPtr cache = m_slots[i];
					while (cache)
					{
						ncount++;
						cache = cache->GetNext();
					}
				}
				return ncount;
			}
			static  HashPair splitHash(std::size_t hash){
				uint8_t tag = (hash & 0x000000ff);// | 0x80;	// 使用低7个bit用于tag,第8个保留用于识别是否为空
				return std::make_pair(hash, tag);
			}


			template<bool largeSize>
			 void PrefetchChunk(CacheLine* chunk)const{
				 if(largeSize)
				 	prefetchAddr((const char*)chunk + (sizeof(CacheLine) >> 1));
			 }

			ChunkIndex Find(KeyType const& key,const HashPair& hp)const{
				int slot = GetPos(hp);
				CacheLine* chunk = m_slots[slot];
				const bool large = sizeof(CacheLine) > 64;
				bool sse2 = sse::supports_sse2();
				while (chunk)
				{
					if (sse2 && large)
						PrefetchChunk<large>(chunk);
					int index = chunk->find(key, hp);
					if (index >= 0)
						return ChunkIndex(chunk, index);
					chunk = chunk->GetNext();
				}
				return ChunkIndex{ nullptr, -1 };
			}

			// 优先使用cacheList单链表来分配CacheLine,如果使用,消耗头部,返回下一个
			// 如果不使用,直接返回下一个,其他情况,与原先的Put相同
			CacheLine* PutWithCache(const KeyType& key, const ValueType& value, CacheLine* cacheList)
			{
				// 上层已经保证不可能重复,不需要查找
				auto hp = splitHash(key.GetHash());
				int slot = GetPos(hp);
				SlotPtr cache = m_slots[slot];
				if (cache && cache->PutWithSpace(key, hp, value))
				{
					m_count++;
					return cacheList;
				}
				if (cacheList)
				{
					cache = cacheList;
					cacheList = cacheList->GetNext();
					cache->Clear();
					cache->SetNext(m_slots[slot]);
				}
				else
					cache = NewCache(cache);
				m_slots[slot] = cache;
				cache->PutDirectly(key, hp, value);
				m_nodecount++;
				m_count++;
				return cacheList;
			}
		public:

			 int GetPos(const HashPair& hashPair)const{
				// 如果长度是2的n次方,那么计算位置的速度会更快,但是会浪费
				// 更多的内存
				// 如果m_slots.size()刚好是2的m_bitcount次幂,那么优化计算方式
				//return m_bitcount != 0 ? (hashPair.first >> m_bitcount)&m_bitmask:
				//	hashPair.first%m_slots.size();
				return (hashPair.first >> m_bitcount)&m_bitmask;
			}
			int  GetBytes()const{
				if (m_flag&kFlagUsePool)
				{
					return sizeof(*this) + m_pool.GetBytes();
				}
				Stat st;
				GetStat(st);
				return st.bytes;
			}
			void  GetStat(Stat& st)const
			{
				int slot_hole = 0;
				for (int i = 0; i < (int)m_slots.size(); i++)
				{
					CacheLine* cache = m_slots[i];
					if (cache)
						cache->GetStat(st);
					else
						slot_hole++;
				}
				st.slot_hole = slot_hole;
				st.slot_count = m_slots.size();
				st.bytes += m_slots.size()*sizeof(SlotPtr);
			}
		};

		//StringIntEntry
		typedef FStringChunk<StringIntEntry, StringView, uint, 256> String256Chunk;
		typedef StringIntHashMap<StringIntEntry, StringView, uint, String256Chunk> StringChunkMap;

		void StringChunkMapTest();
	}//namespace base;
}//namespace ss;
